//方法一：维护两个数组
//一个记录每个位置左边所有数字的乘积；一个记录每个位置右边所有数字的乘积
// class Solution {
// public:
//     vector<int> productExceptSelf(vector<int>& nums) {
//         vector<int> ret;
//         int len = nums.size();
//         vector<int> left(len, 1);
//         vector<int> right(len, 1);

//         for (int i = 1; i < len; i++)
//         {
//             left[i] = left[i - 1] * nums[i - 1];
//             right[len - i - 1] = right[len - i] * nums[len - i];
//         }

//         for (int i = 0; i < len; i++)
//             ret.push_back(left[i] * right[i]);

//         return ret;
//     }
// };

//方法二，用变量代替数组
//将返回的数组看成修改对象
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> ret(len, 1);    //i位置的乘积就是 左边所有数字的积 * 右边所有数字的积
        int left = 0, left_sub = 1; //left_sub表示left左边所有数的乘积
        int right = len - 1, right_sub = 1; //right_sub表示right右边所有数的乘积
        
        for (; left < len; left++, right--)
        {
            ret[left] *= left_sub;  //数组左侧的数，其左边所有数字的乘积已经确定
            ret[right] *= right_sub;    //数组右侧的数，其右边所有数字的乘积已经确定

            left_sub *= nums[left];
            right_sub *= nums[right];
        }

        return ret;
    }
};